/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/self-crossing
   @Language: C++
   @Datetime: 19-05-17 10:30
   */

class Solution {
public:
	/**
	 * @param x: an array of n positive numbers
	 * @return: determine if your path crosses itself
	 * Tip: 4 special states
	 * ┌───┐           ┌───┐  ┌───┐ 
	 * │   │   ┌──┼─┐  │   ┃  │  ─┼┐
	 * └───┼─  └──┘    └───┘  └────┘
	 */
	bool isSelfCrossing(vector<int> &x) {
		// write your code here
		int n=x.size();
		if(n>3 && x[2]<=x[0] && x[3]>=x[1]) return true;
		if(n>4 && x[3]<x[1] && x[4]>=x[2]) return true;
		if(n>4 && x[2]>x[0]){
			if(x[4]>=x[2]-x[0]){
				if(x[3]==x[1]) return true;
				if(x[3]>x[1] && n>5 && x[5]>=x[3]-x[1]) return true;
			}
		}
		for(int i=5; i<n; ++i)
			if(x[i]>=x[i-2]) return true;
		return false;
	}
};
